// 面试题 02.08. 环路检测

// 给定一个链表，如果它是有环链表，实现一个算法返回环路的开头节点。若环不存在，请返回 null。

#include <stdio.h>

struct ListNode
{
    int val;
    struct ListNode *next;
};

struct ListNode *detectCycle(struct ListNode *head)
{
    struct ListNode *slow = head;
    struct ListNode *fast = head;

    while (fast != NULL && fast->next != NULL)
    {
        slow = slow->next;
        fast = fast->next->next;

        //若第一次相遇
        if (slow == fast)
        {   
            //慢指针重置位置再head，fast位置不变
            slow = head;

            //第二次相遇，所在节点就是环的起始节点
            while (slow != fast)
            {
                //快慢指针同时移动一步
                slow = slow->next;
                fast = fast->next;
            }
            return fast;
        }
    }
    return NULL;
}